package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

// 环形链表
type CircularLinkedList struct {
	head *Node
}

// 追加元素
func (list *CircularLinkedList) Append(e interface{}) {

	// 创建待追加的node节点
	node := &Node{
		e:    e,
		next: nil,
	}

	// 链表为空
	if list.head.next == nil {
		list.head = node
		list.head.next = list.head
	} else {
		// 迭代找到尾部元素
		tmp := list.head
		for {
			// 当tmp元素的next是head时表示它是尾部元素
			if tmp.next == list.head {
				break
			}
			tmp = tmp.next
		}
		tmp.next = node
		node.next = list.head
	}
}

// 删除元素
func (list *CircularLinkedList) Remove(
	e interface{},
	comparator func(e1 interface{}, e2 interface{}) int) (r interface{}) {

	if list.head.next == nil {
		return nil
	}

	tmp := list.head.next
	helper := list.head

	for {
		if comparator(tmp.e, e) == 0 {
			break
		}
		if tmp == list.head {
			return nil
		}
		tmp = tmp.next
		helper = helper.next
	}

	if tmp == list.head {
		if tmp.next == tmp {
			list.head = tmp.next
			tmp.next = nil
		} else {
			helper.next = tmp.next
			list.head = tmp.next
		}
	} else {
		helper.next = tmp.next
	}

	return tmp.e
}

// 判断空链表
func (list *CircularLinkedList) IsEmpty() bool {
	return list.head.next == nil
}

// 迭代器
func (list *CircularLinkedList) Iterate() Iterator {
	return &CircularLinkedListIterator{
		current: list.head,
		head:    list.head,
	}
}

// 约瑟夫问题
func (list *CircularLinkedList) JosephuGame(start int, count int) []interface{} {

	if list.head.next == nil {
		return make([]interface{}, 0)
	}

	result := make([]interface{}, 0)

	first := list.head
	last := list.head

	for {
		if last.next == list.head {
			break
		}
		last = last.next
	}

	for i := 1; i < start; i++ {
		first = first.next
		last = last.next
	}

	for {

		for j := 0; j < count; j++ {
			first = first.next
			last = last.next
		}

		result = append(result, first.e)

		first = first.next
		last.next = first

		if first == last {
			break
		}
	}

	result = append(result, first.e)

	return result
}

// 覆盖String方法，格式化输出
func (list CircularLinkedList) String() string {
	next := list.head.next
	// 空链表
	if next == nil {
		return "[]"
	} else {
		s := "["
		tmp := list.head
		for {
			s += fmt.Sprintf("%v, ", tmp.e)
			if tmp.next == list.head {
				break
			}
			tmp = tmp.next
		}
		return strings.TrimRight(strings.TrimSpace(s), ",") + "]"
	}
}

// 表示一个链表节点
type Node struct {
	e    interface{}
	next *Node
}

type Iterator interface {
	HasNext() bool
	Next() interface{}
}

type CircularLinkedListIterator struct {
	current *Node
	head    *Node
}

func (iter *CircularLinkedListIterator) HasNext() bool {
	return iter.current.next != nil && iter.current != iter.head
}

func (iter *CircularLinkedListIterator) Next() interface{} {

	if iter.current.next == nil {
		return nil
	}

	node := iter.current
	iter.current = node.next
	return node.e
}

// 示例元素结构体
type Student struct {
	id       int
	name     string
	nickname string
	star     string
}

// 覆盖String方法，格式化输出
func (student *Student) String() string {
	return fmt.Sprintf("{id=%d, name=%s, nickname=%s, star=%s}", student.id, student.name, student.nickname, student.star)
}

// 读取108将
func read108() (arr []*Student) {

	arr = make([]*Student, 108)

	// 打开文件
	file, err := os.Open("D:\\IdeaProjects\\go-study\\basic-go\\src\\list-demo\\sorted-doubly-linked-list\\108.txt")

	if err != nil {
		fmt.Printf("Open file error: %v\n", err)
		return
	}

	defer func() {
		_ = file.Close()
	}()

	// 创建reader
	reader := bufio.NewReader(file)

	i := 0

	// 读取文件内容
	for {

		line, err := reader.ReadString('\n')

		if err == io.EOF {
			break
		}

		line = strings.TrimRight(line, "\r\n")
		fields := strings.Split(line, "\t")
		id, _ := strconv.Atoi(fields[0])
		arr[i] = &Student{
			id:       id,
			name:     fields[3],
			nickname: fields[2],
			star:     fields[1],
		}
		i++
	}

	return arr
}

func main() {

	_ = func(e1 interface{}, e2 interface{}) int {
		return e1.(*Student).id - e2.(*Student).id
	}

	node := &Node{}

	list := CircularLinkedList{node}

	// 读取108将
	students := read108()

	for _, student := range students {
		list.Append(student)
	}

	// 迭代器
	iterator := list.Iterate()

	for {

		if list.IsEmpty() {
			break
		}

		next := iterator.Next()
		fmt.Printf("迭代元素: %v\n", next)

		if !iterator.HasNext() {
			break
		}
	}

	fmt.Println("---")
	fmt.Println("--- 约瑟夫问题 ---")

	// 约瑟夫问题
	arr := list.JosephuGame(5, 10)
	for _, student := range arr {
		fmt.Printf("出列顺序: %v\n", student)
	}
}
